package search.interpolation;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-04 13:09
 * @ Description : 适用关键字分布较为均匀的数据查找
 */
public class InterpolationSearch
{
    public static void main(String[] args)
    {
        int[] array = new int[100];
        for (int i = 0; i < 100; i++)
        {
            array[i] = i + 1;
        }
        int i = interpolationSearch(array, 0, array.length - 1, 200);
        System.out.println("i = " + i);
    }

    public static int interpolationSearch(int[] array, int left, int right, int findVal)
    {
        //后两个条件防止越界并优化
        if (left > right || findVal < array[0] || findVal > array[array.length - 1])
        {
            return -1;
        }

        //自适应
        int mid = left + (right - left) * (findVal - array[left]) / (array[right] - array[left]);
        int midVal = array[mid];

        if (findVal < midVal)
        {
            return interpolationSearch(array,left,mid - 1,findVal);
        }
        else if (findVal > midVal)
        {
            return interpolationSearch(array,mid + 1, right,findVal);
        }
        else
        {
            return mid;
        }
    }


}
